Round Overview
Discuss this match
TheBlackJackDivTwo
Problem Details
Used as: Division Two - Level One:
Value | 250 |
Submission Rate | 942 / 995 (94.67%) |
Success Rate | 920 / 942 (97.66%) |
High Score | ashishsingh2105 for 249.92 points (0 mins 31 secs) |
Average Score | 221.81 (for 920 correct submissions) |
Straight forward solution , Whenever the first character is digit add the value otherwise when it is ten (T), jack(J),queen(Q) or King(K) the value is 10 and for ace (A) it is 11. This can be done with if’s or switch or a map.
1
2
3
4
5
6
7
8
9
10
11
int score(String[] cards) {
map < char, int > m;
m['T'] = m['J'] = m['Q'] = m['K'] = 10;
m['A'] = 11;
for (i = 0; i < cards.size(); i++) {
char ch = cards[i][0];
if (isdigit(ch)) sum += ch - '0';
else sum += m[ch];
}
return sum;
}
The problem can be solved also without using maps.
1
2
3
4
5
6
7
8
int score(vector < string > cards) {
int res = 0;
for (int i = 0; i < (int) cards.size(); i++)
if (cards[i][0] == 'A') res += 11;
else if (isdigit(cards[i][0])) res += cards[i][0] - '0';
else res += 10;
return res;
}
TheCardShufflingDivTwo
Problem Details
Used as: Division Two - Level Two:
Value | 500 |
Submission Rate | 577 / 995 (57.99%) |
Success Rate | 153 / 577 (26.52%) |
High Score | Gordeev for 495.00 points (2 mins 51 secs) |
Average Score | 292.88 (for 153 correct submissions) |
Easy solution A straight forward simulation times out. Because each operation requires O(n) changes and there are m such operations. So O(n*m) would get TLE. For the first operation we see that all the even numbers come first , then the odd numbers in increasing order. Say n=2*k. we get the middle deck after first operation as 2,4,6,8,…n,1,3,5.7…n-1. By this we can find a mapping , position 1 is taken by 2 , 2 is taken by 4… and something is taken by 1. This mean we get a cycle . Find the cycle length mod m. For n=5, the cycle is 1->2->4->3->1 , after every 4 operations the cycle repeats. Since n=10^6 we can find cycle length in O(n) and it works fine.
Another solution goes by . Say n=2*k+1. we get the middle deck after first operation as 2,4,6,8,…n-1,1,3,5.7…n.The next sequence is 4 8…
* Now this becomes the original sequence for the next iteration.So our first position is numbers occurring at positions like 1,2,4,8 , this tell if n is even our first position will be a power of 2. Say n=5, so until 4 we get the first position, the next position is 8 if the list had been that big but since n=5, it will wrap around and we get 3. So for n=2*k+1 we get position 2^m%n.but for even (n) several of the 2^m will be divisible by n which will make it 0. But when n=2*k+1 we can see that n maps to itself ie the position n never comes to the first place. So for odd numbers that last number can never take the first place. So for n=even we add a dummy number n+1 and make the length n+1. So we get 2^m %(n+1). n=1 is special case because it divides everything.
See this solution for the former approach scaulyd solution
other solution
1
2
3
4
5
6
7
8
9
10
11
12
int fpow(int x, int y, int c) {
if (y == 1) return x % c;
long long k = fpow(x, y / 2, c);
k = k * k;
k %= c;
if (y & 1) return k * x % c;
else return k;
}
int shuffle(int n, int m) {
if (n == 1) return 1;
return fpow(2, m, n + !(n & 1));
}
TheCardLineDivTwo
Problem Details
Used as: Division Two - Level Three:
Value | 000 |
Submission Rate | 123 / 995 (12.36%) |
Success Rate | 24 / 123 (19.51%) |
High Score | TTLovePP for 820.49 points (13 mins 56 secs) |
Average Score | 617.20 (for 24 correct submissions) |
Analysis
we see the number MOD=1234567891, x%MOD can take max value of 1234567890. So if we add numbers %MOD it can be at max 2*(MOD-1) > 2^31 -1.
So it can’t be stored in plain int , use unsigned int or long long. Once the datatype is fixed, we proceed on to the solution
Let each card be a vertex and there be edges between vertices if we have same color or value. So we build the adjacency matrix for a graph, call it M.
Now if it is a complete graph the answer is n! because all the permutations are valid . If we have some way of generating all the permutations and checking them if they are valid it gives us the answer. It works until n=10 . But for n=16 we need something better.
if we represent the number of vertices by a bitmask whenever we reach (1<<n)-1 we have a path so whenever the bitmask is (1<<n) -1 we return 1 otherwise 0.
If we starting from a vertex p we can reach bitmasks m1,m2,m3 , we can store the solutions we get . Lots of vertices may go to p at some point with masks m1,m2,m3 , since we have saved up the answer for p with masks , we can return them without computing.
Look at the Dp solution of TTLovePP’s solution
TheBlackJackDivOne
Problem Details
Used as: Division One - Level One:
Value | 250 |
Submission Rate | 482 / 683 (70.57%) |
Success Rate | 427 / 482 (88.59%) |
High Score | ACRush for 242.61 points (4 mins 59 secs) |
Average Score | 157.98 (for 427 correct submissions) |
We are given certain number (K) of cards with value V.Let the count of remaining cards of value 2,3,…11 be R2,R3,…R11
The probability of choosing Rk with C cards remaining is Rk/C. It increases the value (V) by k.
One way of looking at ans=1.0 is whenever we have a value less than 21, we have to take atleast 1 more card and then use the probability of that card, the other being if p is the prob of choosing this card then
1
E(x) = p * (1 + E[x + new]), ie after 1 move with probability p we move into new step E[x + new]
where new is the value of card.
*There are around 40000 states to be examined.
1
2
3
4
5
6
7
8
9
10
11
12
// cnt contains the remaining count of each value available after deducting what is given.
int go(int have, int C) {
if (have >= 21) return 0.0; // Expected number of cards required
double ans = 1.0;
for (i = 2; i < 12; i++) {
if (cnt[i]) {
double prob = cnt[i] * 1. / C;
ans += prob * go(have + i, C + 1);
}
}
return ans;
}
Look at any of the Accepted solutions or the thread discussion
TheCardShufflingDivOne
Problem Details
Used as: Division One - Level Two:
Value | 500 |
Submission Rate | 112 / 683 (16.40%) |
Success Rate | 73 / 112 (65.18%) |
High Score | Petr for 458.79 points (8 mins 40 secs) |
Average Score | 269.74 (for 73 correct submissions) |
TheCardLineDivOne
Problem Details
Used as: Division One - Level Three:
Value | 1000 |
Submission Rate | 12 / 683 (1.76%) |
Success Rate | 2 / 12 (16.67%) |
High Score | Petr for 471.22 points (41 mins 41 secs) |
Average Score | 456.78 (for 2 correct submissions) |